package com.gitee.feizns.explore.data_structure.graph;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * @author feizns
 * @since 2020/5/7
 */
public class ShortestAlternatingPaths {

    //5
    //[[0,1],[1,2],[2,3],[3,4]]
    //[[1,2],[2,3],[3,1]]
    public static void main(String[] args) {
//        System.out.println(Arrays.toString(new ShortestAlternatingPaths().shortestAlternatingPaths(3, new int[][]{{0, 1}, {0, 2}}, new int[][]{{1, 0}})));
        System.out.println(Arrays.toString(new ShortestAlternatingPaths().shortestAlternatingPaths(3, new int[][]{{0, 1}, {0, 2}}, new int[][]{{1, 0}})));
    }

    public int[] shortestAlternatingPaths(int n, int[][] red_edges, int[][] blue_edges) {
        this.graph = create(n, red_edges, blue_edges);
        ans = new int[n];
        for (int i = 0; i < ans.length; i++)
            ans[i] = -1;

        visited(n);
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        bfs(queue, Color.RED);

        visited(n);
        queue.add(0);
        bfs(queue, Color.BLUE);

        return ans;
    }

    private void visited(int size) {
        visited = new boolean[size][];
        for (int i = 0; i < size; i++)
            visited[i] = new boolean[2];
    }

    private void bfs(Queue<Integer> queue, Color c) {
        int level = 0;
        boolean red = (Color.RED == c);
        while ( !queue.isEmpty() ) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cur = queue.remove();
                ans[cur] = Math.min(level, ans[cur]);
                if ( red ) {
                    for (int v : graph.edg[cur].reds) {
                        if ( !visited[v][Color.RED.val] ) {
                            visited[v][Color.RED.val] = true;
                            queue.add(v);
                        }
                    }
                } else {
                    for (int v : graph.edg[cur].blue) {
                        if ( !visited[v][Color.BLUE.val] ) {
                            visited[v][Color.BLUE.val] = true;
                            queue.add(v);
                        }
                    }
                }
            }
            level++;
        }
    }

    private boolean[][] visited;

    private int[] ans;

    private Graph graph;

    private Graph create(int n, int[][] red_edges, int[][] blue_edges) {
        Graph graph = new Graph(n);
        for (int i = 0; i < red_edges.length; i++)
            graph.add(red_edges[i][0], red_edges[i][1], Color.RED);
        for (int i = 0; i < blue_edges.length; i++)
            graph.add(blue_edges[i][0], blue_edges[i][1], Color.BLUE);
        return graph;
    }

    private static class Graph {
        private Node[] edg;
        public Graph(int size) {
            this.edg = new Node[size];
            for (int i = 0; i < size; i++)
                edg[i] = new Node();
        }
        public void add(int s, int t, Color color) {
            if ( color == Color.RED )
                edg[s].reds.add(t);
            if ( color == Color.BLUE )
                edg[s].blue.add(t);
        }
    }

    private static class Node {
        Set<Integer> reds = new HashSet<>();
        Set<Integer> blue = new HashSet<>();
    }

    private enum Color {
        RED(0),
        BLUE(1);
        int val;
        Color(int val) {
            this.val = val;
        }
    }

}
